package com.example.leetcode.search;


//双指针
/**
 * 旋转数组的最小数字

 旋转数组将原本有序的数组分成了两部分有序的数组，因为在原始有序数组中，最小的元素一定是在首位，
 旋转后无序的点就是最小的数字。我们可以将旋转前的前半段命名为A，旋转后的前半段命名为B，
 旋转数组即将AB变成了BA，我们想知道最小的元素到底在哪里。
 因为A部分和B部分都是各自有序的，所以我们还是想用分治来试试，每次比较中间值，确认目标值（最小元素）所在的区间。
 */
public class MinNumberInRotateArray {

    public int minNumberInRotateArray (int[] nums) {
        int left = 0;
        int right = nums.length -1;

        while(left < right) {
            int mid = (left + right) / 2;

            // 最小值在右边（右边的元素都是比mid小并且还都是有序的）
            if(nums[mid] > nums[right]) {
                left = mid +1;
                // 一个一个试
            } else if (nums[mid] == nums[right]){
                right--;
            } else{
                // 最小值在左边或者就是mid
                right = mid ;
            }
        }


        return nums[left];
    }
}
